# -*- coding: utf8 -*-
"""
Combinatorial object : Parking functions

.. TODO:: try to implement with Florent Hivert's factories

AUTHOR:

- Jean-Baptiste Priez
"""
#*****************************************************************************
#       Copyright (C) 2012 Jean-Baptiste Priez <jbp@kerios.fr>,
#
#  Distributed under the terms of the GNU General Public License (GPL)
#
#    This code is distributed in the hope that it will be useful,
#    but WITHOUT ANY WARRANTY; without even the implied warranty of
#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
#    General Public License for more details.
#
#  The full text of the GPL is available at:
#
#                  http://www.gnu.org/licenses/
#*****************************************************************************
from sage.categories.finite_enumerated_sets import FiniteEnumeratedSets
from sage.combinat.set_partition_ordered import OrderedSetPartitions
from sage.combinat.tools import transitive_ideal
from sage.misc.classcall_metaclass import ClasscallMetaclass
from sage.misc.lazy_attribute import lazy_attribute, lazy_class_attribute
from sage.rings.integer import Integer
from sage.sets.disjoint_union_enumerated_sets import DisjointUnionEnumeratedSets
from sage.sets.family import Family
from sage.sets.non_negative_integers import NonNegativeIntegers
from sage.sets.set import Set
from sage.structure.list_clone import ClonableIntArray
from sage.structure.parent import Parent
from sage.structure.unique_representation import UniqueRepresentation

def _d_( word ):
    '''
    d(w) = min{i>=1 I #{w_j <= i} < i}

    TESTS::

        sage: from sage.combinat.some_hopf_algebra.parking_functions import _d_
        sage: _d_([1,1,4])
        3
        sage: _d_([4,2])
        1
        sage: _d_([1,1,1,2])
        5
    '''
    sort = sorted( list( word ) )
    for i in range( 1, len( sort ) + 1 ):
        if sort[i - 1] > i :
            return i
    return len( sort ) + 1

def to_park2( li ):
    """
    TESTS::

        sage: from sage.combinat.some_hopf_algebra.parking_functions import to_park2
        sage: to_park([1,1,1,5])
        [1, 1, 1, 4]
        sage: to_park([1,2,4,5])
        [1, 2, 3, 4]
        sage: to_park([3,1,2,4,5])
        [3, 1, 2, 4, 5]
    """
    nli = list( li )
    n = len( li )
    d = _d_( nli )

    while d < n + 1:
        nli = [i if i <= d else i - 1 for i in nli]
        d = _d_( nli )
    return ParkingFunction( nli )

def to_park( word ):
    """
    TESTS::

        sage: from sage.combinat.some_hopf_algebra.parking_functions import to_park
        sage: to_park([1,1,1,5])
        [1, 1, 1, 4]
        sage: to_park([1,2,4,5])
        [1, 2, 3, 4]
        sage: to_park([3,1,2,4,5])
        [3, 1, 2, 4, 5]
    """
    if len( word ) == 0:
        return ParkingFunction( [] )
    import collections
    dic_pos = collections.defaultdict( list )
    for pos in range( len( word ) ):
        dic_pos[word[pos]].append( pos )
    i = 1; lt = min( word )
    w = {}
    for l in sorted( dic_pos.keys() ):
        i = min( i + abs( l - lt ), len( w.keys() ) + 1 )
        lt = l
        for pos in dic_pos[l]:
            w[pos] = i
    return ParkingFunction( w.values() )

class ParkingFunction( ClonableIntArray ):
    """
    The class of parking functions

    .. TODO:: tests
    """
    __metaclass__ = ClasscallMetaclass

    @staticmethod
    def __classcall_private__( cls, *args, **opts ):
        """
        Ensure that parking function created by the enumerated sets and directly
        are the same and that they are instances of :class:`ParkingFunction`

        ..TODO::tests

            sage: from sage.combinat.some_hopf_algebra.parking_functions import ParkingFunctions_all, ParkingFunctions, ParkingFunction
            sage: issubclass(ParkingFunctions_all().element_class, ParkingFunction)
            True
            sage: w0 = ParkingFunction([4,2,1,1,2])
            sage: w0.parent()
            Parking Functions
            sage: type(w0)
            <class 'sage.combinat.some_hopf_algebra.parking_functions.ParkingFunctions_all_with_category.element_class'>
            sage: w1 = ParkingFunctions()([4,1,1,1,2])
            sage: w1.parent() is w0.parent()
            True
            sage: type(w1) is type(w0)
            True
        """
        return cls._auto_parent.element_class( cls._auto_parent, *args, **opts )

    @lazy_class_attribute
    def _auto_parent( self ):#(cls):
        """
        The automatic parent of the element of this class

        When calling the constructor of an element of this class, one needs a
        parent. This class attribute specifies which parent is used.

        ..TODO::examples::

            sage: from sage.combinat.some_hopf_algebra.parking_functions import ParkingFunction
            sage: ParkingFunction._auto_parent
            Parking Functions
            sage: ParkingFunction().parent()
            Parking Functions
         """
        return ParkingFunctions_all()

    def __init__( self, parent, li = None, check = True ):
        """
        TESTS::

            sage: from sage.combinat.some_hopf_algebra.parking_functions import ParkingFunction
            sage: ParkingFunction([]).parent()
            Parking Functions
        """
        if li is None:
            li = []
        ClonableIntArray.__init__( self, parent, li, check = check )

    def check( self ):
        """
        Checks that ``self`` is a packed word

        TESTS::

            sage: from sage.combinat.some_hopf_algebra.parking_functions import ParkingFunction
            sage: ParkingFunction([3,3,1,1])
            [3, 3, 1, 1]

            #sage: ParkingFunction([2,2,1,0,4])
            #Traceback (most recent call last)
            #...
            #AssertionError: This is not a packed word
        """
        from sage.combinat.non_decreasing_parking_function import NonDecreasingParkingFunctions
        s = Set( list( self ) )
        assert( sorted( list( self ) ) in NonDecreasingParkingFunctions() ), "This is not a parking function %s" % str( self )

    def is_empty( self ):
        """
        Returns whether ``self`` is the empty word.

        EXAMPLES::

            sage: from sage.combinat.some_hopf_algebra.parking_functions import ParkingFunction
            sage: ParkingFunction().is_empty()
            True
            sage: ParkingFunction([]).is_empty()
            True
            sage: ParkingFunction([2,1,2]).is_empty()
            False
        """
        return not self

    def size( self ):
        """
        EXAMPLES::

            sage: from sage.combinat.some_hopf_algebra.parking_functions import ParkingFunction
            sage: ParkingFunction().size()
            0
            sage: ParkingFunction([2,1,1]).size()
            3
        """
        return len( self )

#===============================================================================
# Abstract class to serve as a Factory no instance are created
#===============================================================================

class ParkingFunctions( UniqueRepresentation, Parent ):
    """
    Factory class for parking functions.

    INPUT:

    - ``size`` -- (optional) an integer

    OUTPUT:

    - the set of all packed words (of ``size`` (if specified))

    TESTS::

        sage: from sage.combinat.some_hopf_algebra.parking_functions import ParkingFunctions
        sage: TestSuite(ParkingFunctions()).run()


    EXAMPLES::

        sage: from sage.combinat.some_hopf_algebra.parking_functions import ParkingFunctions
        sage: ParkingFunctions()
        Parking Functions
        sage: ParkingFunctions(4)
        Parking functions of size 4
    """
    @staticmethod
    def __classcall_private__( cls, n = None ):
        """
        TESTS::

            sage: from sage.combinat.some_hopf_algebra.parking_functions import ParkingFunctions, ParkingFunctions_size, ParkingFunctions_all
            sage: isinstance(ParkingFunctions(2), ParkingFunctions)
            True
            sage: isinstance(ParkingFunctions(), ParkingFunctions)
            True
            sage: ParkingFunctions(2) is ParkingFunctions_size(2)
            True
            sage: ParkingFunctions(5).cardinality()
            1296
            sage: ParkingFunctions() is ParkingFunctions_all()
            True
        """
        if n is None:
            return ParkingFunctions_all()
        else:
            assert( isinstance( n, ( Integer, n ) ) and n >= 0 ), "n must be a non negative integer"
            return ParkingFunctions_size( Integer( n ) )

#===============================================================================
# Enumerated set of all packed words     
#===============================================================================
class ParkingFunctions_all( DisjointUnionEnumeratedSets, ParkingFunctions ):

    def __init__( self ):
        """
        TESTS::

            sage: from sage.combinat.some_hopf_algebra.parking_functions import ParkingFunctions_all
            sage: P = ParkingFunctions_all()
            sage: P.cardinality()
            +Infinity
            sage: it = iter(P)
            sage: (it.next(), it.next(), it.next(), it.next(), it.next(), it.next())
            ([], [1], [1, 1], [1, 2], [2, 1], [1, 1, 1])
            sage: it.next().parent()
            Parking Functions
            sage: P([])
            []
            sage: P is ParkingFunctions_all()
            True
            sage: TestSuite(P).run()
        """
        DisjointUnionEnumeratedSets.__init__( 
            self, Family( NonNegativeIntegers(), ParkingFunctions_size ),
            facade = True, keepkey = False )

    def _repr_( self ):
        """
        TESTS::

            sage: from sage.combinat.some_hopf_algebra.parking_functions import ParkingFunctions
            sage: ParkingFunctions()
            Parking Functions
        """
        return "Parking Functions"

    def __contains__( self, x ):
        """
        TESTS::

            sage: from sage.combinat.some_hopf_algebra.parking_functions import ParkingFunctions,ParkingFunction
            sage: P = ParkingFunctions()
            sage: 1 in P
            False
            sage: ParkingFunction([]) in P
            True
        """
        return isinstance( x, self.element_class )

    def __call__( self, x = None, *args, **keywords ):
        """
        Ensure that ``None`` instead of ``0`` is passed by default.

        TESTS::

            sage: from sage.combinat.some_hopf_algebra.parking_functions import ParkingFunctions
            sage: P = ParkingFunctions()
            sage: P()
            []
        """
        return super( ParkingFunctions, self ).__call__( x, *args, **keywords )

    def _element_constructor_( self, *args, **keywords ):
        """
        EXAMPLES::

            sage: from sage.combinat.some_hopf_algebra.parking_functions import ParkingFunctions
            sage: P = ParkingFunctions()
            sage: P._element_constructor_()
            []
            sage: P()
            []
            sage: P([1,1,3])
            [1, 1, 3]
        """
        return self.element_class( self, *args, **keywords )

    Element = ParkingFunction

#===============================================================================
# Enumerated set of packed words of a given size
#===============================================================================
class ParkingFunctions_size( ParkingFunctions ):
    """
    TESTS::

        sage: from sage.combinat.some_hopf_algebra.parking_functions import ParkingFunctions_size
        sage: TestSuite(ParkingFunctions_size(5)).run()
        sage: TestSuite(ParkingFunctions_size(7)).run()

    """

    def __init__( self, size ):
        super( ParkingFunctions_size, self ).__init__( category = FiniteEnumeratedSets() )
        self._size = size

    def _repr_( self ):
        """
        TESTS::

            sage: from sage.combinat.some_hopf_algebra.parking_functions import ParkingFunctions
            sage: ParkingFunctions(4)
            Parking functions of size 4
        """
        return "Parking functions of size %s" % ( self._size )

    def __contains__( self, x ):
        """
        TESTS::

            sage: from sage.combinat.some_hopf_algebra.parking_functions import ParkingFunctions, ParkingFunction
            sage: P = ParkingFunctions(4)
            sage: 1 in P
            False
            sage: ParkingFunction([]) in P
            False
            sage: ParkingFunction([1,2,1,3,1,4]) in P
            False
            sage: ParkingFunction([1,2,1,3]) in P
            True
            sage: [1,1,3,3] in P
            False
        """
        return isinstance( x, self.element_class ) and x.size() == self._size

    def _an_element_( self ):
        """
        TESTS::

            sage: from sage.combinat.some_hopf_algebra.parking_functions import ParkingFunctions
            sage: ParkingFunctions(6).an_element()
            [1, 1, 1, 1, 1, 1]
        """
        return self.first()

    def cardinality( self ):
        """
        (n+1)^(n+1)

        TESTS::

            sage: from sage.combinat.some_hopf_algebra.parking_functions import ParkingFunctions_size
            sage: ParkingFunctions_size(0).cardinality()
            1
            sage: ParkingFunctions_size(1).cardinality()
            1
            sage: ParkingFunctions_size(2).cardinality()
            3

        """
        n = self._size
        return ( n + 1 ) ** ( n - 1 )

    def __iter__( self ):
        """
        TESTS::

            sage: from sage.combinat.some_hopf_algebra.parking_functions import ParkingFunctions_size
            sage: list(ParkingFunctions_size(0))
            [[]]
            sage: list(ParkingFunctions_size(1))
            [[1]]
            sage: list(ParkingFunctions_size(2))
            [[1, 1], [1, 2], [2, 1]]
            sage: list(ParkingFunctions_size(3))
            [[1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 1, 3], [1, 3, 1], [1, 2, 2], [2, 1, 2], [1, 2, 3], [2, 1, 3], [1, 3, 2]]
        """
        from sage.combinat.non_decreasing_parking_function import NonDecreasingParkingFunctions
        n = self._size
        if n == 0:
            yield self._element_constructor_()
        else:
            NDPF = NonDecreasingParkingFunctions( n )
            rise = lambda perm: [i for i in range( 0, n - 1 ) if perm[i] < perm[i + 1]]
            for ndpf in NDPF :
                yield self._element_constructor_( ndpf )
                for i in rise( ndpf ) :
                    pf = ndpf[:]
                    pf[i] = ndpf[i + 1]
                    pf[i + 1] = ndpf[i]
                    yield self._element_constructor_( pf )

    @lazy_attribute
    def _parent_for( self ):
        """
        The parent of the element generated by ``self`

        TESTS::

            sage: from sage.combinat.some_hopf_algebra.parking_functions import ParkingFunctions
            sage: P = ParkingFunctions(4)
            sage: P._parent_for
            Parking Functions
        """
        return ParkingFunctions_all()

    @lazy_attribute
    def element_class( self ):
        """
        TESTS::

            sage: from sage.combinat.some_hopf_algebra.parking_functions import ParkingFunctions
            sage: P = ParkingFunctions(4)
            sage: P.element_class
            <class 'sage.combinat.some_hopf_algebra.parking_functions.ParkingFunctions_all_with_category.element_class'>
            sage: P.first().__class__ == ParkingFunctions().first().__class__
            True
        """
        return self._parent_for.element_class

    def _element_constructor_( self, *args, **keywords ):
        """
        EXAMPLES::

            sage: from sage.combinat.some_hopf_algebra.parking_functions import ParkingFunctions
            sage: P = ParkingFunctions(0)
            sage: P([])
            []

            # sage: P([1])
            # Traceback (most recent call last)
            # ...
            # ValueError: Wrong size of word
        """
        res = self.element_class( self._parent_for, *args, **keywords )
        if res.size() != self._size:
            raise ValueError, "Wrong size of word"
        return res
